package com.imooc.distributedemo.resume.arith.treeNode;


import java.util.Deque;
import java.util.LinkedList;

public class TreeNodeSolution {
    public static TreeNode initBtree(int[] elements,int size){
        if(size < 1){
            return null;
        }
        TreeNode[] nodes = new TreeNode[size];
        // 将int数组转换为TreeNode节点
        for (int i = 0; i < size; i++) {
            if(elements[i] == 0){
                nodes[i] = null;
            }else{
                nodes[i] = new TreeNode(elements[i]);
            }
        }
        Deque<TreeNode> q = new LinkedList<>();

        TreeNode node = new TreeNode();
        TreeNode head = nodes[0];
        q.addFirst(nodes[0]);
        int index = 1;
        while (index < size){
            node = q.removeFirst(); // 抛出队首元素
            q.addLast(nodes[index++]); // 加到队尾

            node.left = q.peekLast();
            q.addLast(nodes[index++]);
            node.right = q.peekLast();

        }
        return head;
    }

    // 前序遍历
    public static void preorder(TreeNode root){
        if(root == null) {
            return;
        }
        if(root.val == 0 ){
            System.out.println("nil");
        }else {
            System.out.println(root.val);
        }
        preorder(root.left);
        preorder(root.right);
    }

    public static void main(String[] args) {
        int[] elements = {3,9,20,0,0,15,7}; // 0标示空
        TreeNode root = initBtree(elements,7);
        preorder(root);
        System.out.println("pause");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}